1. Field of Invention
This invention is directed to a method and system for efficiently solving computationally hard problems. In particular, this invention is directed to a method and system for efficiently allocating computing resources between a plurality of different solution procedures for solving the computationally hard problem. Specifically, this invention is directed to a method and system for allocating computer resources to the plurality of different solution procedures based on solution performance and risk factors.
2. Description of Related Art
There are many computationally hard or computationally intensive classes of problems for which no efficient general solution exists. In these classes of computationally hard problems, because of the combinatorics involved, the solution times for such computationally hard problems grow exponentially as the size of the problem grows arithmetically. This exponential growth makes it impossible to solve very large instances of such problems in reasonable times. This is a basic trait of the so-called NP-complete class of problems. Such extremely hard computational problems are pervasive, and exist in fields ranging from molecular biology, to physics, to operations research. Examples of such computationally harder problems include determining the most probable arrangement of cloned fragments of a DNA sequence; the global minima of complicated energy functions in physical and chemical systems; and the shortest path visiting a set of cities.
To attempt to solve these computationally hard problems, for which no generalized solution exists, a number of efficient heuristic methods have been developed. These methods, although not always guaranteed to produce a good solution or to finish in a reasonable time, often provide satisfactory answers fairly quickly. In practice, the performance of these heuristic methods varies greatly from one type of problem to another, within different instances of the same type of problem, and even within different trials of the same problem. That is, in many cases, the heuristic methods involve using randomized procedures, which give rise to performance variability even within repeated trials on a single problem instance.
In addition to the combinatorial search problems outlined above, there are many other computational situations where performances vary from one trial to another. For example, programs operating in large distributed systems or interacting with a physical world can perform unpredictably, due to changes in their operating environment. One familiar example is the action of retrieving a particular web page on the World Wide Web from a remote node on the Internet. In this case, the usual network congestion, which is highly variable, even on a second-by-second basis, leads to a variability in the time required to retrieve the page. This raises the familiar dilemma of determining whether to restart the retrieval process or wait for the current retrieval request to complete.